package acwing.prefixSumAndDifferenceArray;

public class note {
    /**
     * 一维数组前缀和
     * 前缀和: sum[i] = a[1] + a[2] + ... + a[i], 其中sum[0] = 0
     * [left,right]的前缀和 = sum[right] - sum[left - 1]
     * [1,right]的前缀和 = sum[right] - sum[1 - 1] = sum[right] - sum[0] = sum[right]
     *
     * 二维数组前缀和
     * sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j]
     * [x1,y1]与[x2,y2]之间的前缀和
     * res = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]
     *
     * 一维数组差分
     * 有a[1] a[2] ... a[i]
     * 则有数组b, 使得a[i] = b[1] + b[2] + ... + b[i]
     * 则数组b就是数组a的差分数组
     * 给[l,r]区间的数组中每个元素进行+C, 则给b[l] + C, b[r + 1] - C即可
     * 因为 a[l] = b[1] + b[2] + ... + b[l] + C
     * [l,r]区间内的a, 都加了C, 且r之后的a也加了C, 这时需要b[r + 1] - C来保证r之后的a不变.
     */
}
